package Solutions;

import java.util.Arrays;

/***
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
 * 找出 nums 中的三个整数，使得它们的和与 target 最接近。
 * 返回这三个数的和。假定每组输入只存在唯一答案。
 * 示例：
 *
 * 输入：nums = [-1,2,1,-4], target = 1
 * 输出：2
 * 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum-closest
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ThreeSumClosest {
    /***
     * 排序 + 双指针
     * @param nums 传入待分析的数组
     * @param target 给定的目标值
     * @return 最接近目标值的和
     */
    public int threeSumClosest(int[] nums, int target) {
        int result = 0, start, end;
        if (nums.length < 4) { // 当数组的长度小于4的时候，不用分析，直接返回数组所有元素的和即可
            for (int num : nums) {
                result += num;
            }
            return result;
        }
        Arrays.sort(nums);// 排序，有助于分析，提高分析效率同时降低遍历分析的难度
        int a, b, c, jude = Integer.MAX_VALUE, abs, tmp;// jude 是用于分析得到的值与目标值的差异，可以根据根据该值筛选解
        for (int i = 0; i < nums.length - 2; i++) {// 遍历数组，出去最后两个元素
            start = i + 1;// 起始指针
            end = nums.length - 1;// 终止指针
            a = nums[i];// 组成解的第一个元素
            while (start != end) {// 当两个指针重合的时候，退出 while loop
                b = nums[start];// 组成解的第二个元素
                c = nums[end];// 组成解的第三个元素
                tmp = a + b + c;// 计算三者之和作为临时解，并用于后续的分析
                abs = Math.abs(tmp - target);// 计算 abs 的值
                if (abs < jude) {// 如果找到一个比当前的 jude 更小的值，说明该解为更优解
                    jude = abs;// 将 jude 赋值为 abs
                    result = tmp;// 结果赋值为 tmp
                }
                // 该判断部分是为了决定两个指针的移动方向，根据数组已经是排好序的，可以很快的得到移动方案
                if (tmp > target) {// 当当前的临时解 > 目标值 ： 为使得更快地靠近 target 将 end--
                    end--;
                    while (end > start && nums[end] == nums[end + 1]) end--;// 跳过重复使用过的值
                } else if (tmp < target) {// 原理同上
                    start++;
                    while (start < end && nums[start] == nums[start - 1]) start++;
                } else return result;// 当 tmp == target 的时候，result 肯定被赋值为 tmp 此时为最优解，直接返回 result 即可
            }
        }
        return result;// 在程序段的末尾返回结果 result.
    }

    /***
     * 执行结果：
     * 通过
     * 显示详情
     * 执行用时：5 ms, 在所有 Java 提交中击败了 96.30% 的用户
     * 内存消耗：38.5 MB, 在所有 Java 提交中击败了 50.82% 的用户
     */
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 4, 8, 16, 32, 64, 128};
        System.out.println(new ThreeSumClosest().threeSumClosest(nums, 82));
    }
}
